#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 可获得的最大点数
class Solution
{
public:
    int maxScore(vector<int> &cardPoints, int k)
    {
        // 计算连续n-k个的最小值
        int n = cardPoints.size();
        int windowsSize = n - k;
        // 选前n-k个数作为初始值
        int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowsSize, 0);
        int minSum = sum;
        for (int i = windowsSize; i < n; i++)
        {
            // 左边出窗口一个,右边进窗口一个值
            sum += cardPoints[i] - cardPoints[i - windowsSize];
            minSum = min(sum, minSum);
        }

        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
    }
};

// 最大子数组和
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        // dp[i]:表示i位置为结尾的最大子数组和
        // dp[i] = max(nums[i],nums[i] + dp[i - 1])
        int n = nums.size(), ans = INT_MIN;
        vector<int> dp(n);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ans = max(ans, dp[i]);
        }
        return max(ans, dp[0]);
    }
};

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        // dp[i]:表示i位置为结尾的最大子数组和
        // dp[i] = max(nums[i],nums[i] + dp[i - 1])
        int n = nums.size(), ans = INT_MIN;
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++)
        {
            dp[i] = max(nums[i - 1], nums[i - 1] + dp[i - 1]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

// 将二叉搜索树转化为排序的双向链表
class Node
{
public:
    int val;
    Node *left;
    Node *right;

    Node() {}

    Node(int _val)
    {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node *_left, Node *_right)
    {
        val = _val;
        left = _left;
        right = _right;
    }
};
class Solution
{
public:
    Node *prev, *head;
    Node *treeToDoublyList(Node *root)
    {
        if (root == nullptr)
            return nullptr;
        dfs(root);
        head->left = prev;
        prev->right = head;
        return head;
    }

    void dfs(Node *cur)
    {
        if (cur == nullptr)
            return;
        dfs(cur->left);
        if (prev != nullptr)
            prev->right = cur;
        else
            head = cur;
        cur->left = prev;
        prev = cur;
        dfs(cur->right);
    }
};

// 验证二叉搜索树的后续遍历序列
// 划分左右子树： 遍历后序遍历的 [i,j] 区间元素，寻找 第一个大于根节点 的节点，索引记为 m 此时，可划分出左子树区间 [i,m−1] 右子树区间 [m,j−1] 根节点索引 j
// 判断是否为二叉搜索树：
// 左子树区间 [i,m−1] 内的所有节点都应 < postorder[j] 而第 1.划分左右子树 步骤已经保证左子树区间的正确性，因此只需要判断右子树区间即可。
// 右子树区间 [m,j−1] 内的所有节点都应 > postorder[j] 实现方式为遍历，当遇到 ≤postorder[j] 的节点则跳出；则可通过 p=j 判断是否为二叉搜索树。
class Solution
{
public:
    bool verifyTreeOrder(vector<int> &postorder)
    {
        return recur(postorder, 0, postorder.size() - 1);
    }

    bool recur(vector<int> &postorder, int i, int j)
    {
        if (i >= j)
            return true;
        int p = i;
        while (postorder[p] < postorder[j])
            p++;
        // m为右子树的起始位置
        int m = p;
        while (postorder[p] > postorder[j])
            p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
};

// 最长公共前缀
class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        string ans = strs[0];
        for (int i = 1; i < strs.size(); i++)
        {
            ans = findPrefix(ans, strs[i]);
        }

        return ans;
    }

    string findPrefix(string &s1, string &s2)
    {
        int i = 0;
        while (i < s1.size() && i < s2.size() && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
};

class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        for (int i = 0; i < strs[0].size(); i++)
        {
            char ch = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
            {
                if (ch != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }

        return strs[0];
    }
};

// 最小栈
class MinStack
{
private:
    stack<int> st;
    stack<int> min_st;

public:
    MinStack()
    {
    }

    void push(int val)
    {
        st.push(val);
        if (min_st.empty() || val <= min_st.top())
            min_st.push(val);
        else
            min_st.push(min_st.top());
    }

    void pop()
    {
        st.pop();
        min_st.pop();
    }

    int top()
    {
        return st.top();
    }

    int getMin()
    {
        return min_st.top();
    }
};
